﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/next-greater-node-in-linked-list/
/*
题目描述：
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，
这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。
如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
*/

// 开始解题：
 // 方法1——暴力二层循环
int* nextLargerNodes(struct ListNode* head, int* returnSize) {
    if (NULL == head) {
        return NULL;
    }
    struct ListNode* cur1 = head;
    int len = 0;
    while (cur1) {
        len++;
        cur1 = cur1->next;
    }
    *returnSize = len;
    // 创建数组answer
    int* answer = (int*)malloc(len * sizeof(int));
    if (NULL == answer) {
        perror("malloc fail");
        return NULL;
    }
    cur1 = head;
    int n = 0;
    struct ListNode* cur2 = cur1->next;
    while (cur1) {
        cur2 = cur1->next;
        while (cur2) {
            if (cur2->val > cur1->val) {
                answer[n] = cur2->val;
                n++;
                break;
            }
            cur2 = cur2->next;
        }
        if (NULL == cur2) {
            answer[n] = 0;
            n++;
        }
        cur1 = cur1->next;
    }
    return answer;
}
